home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 17131 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.0 KB
  1. Path: prairienet.org!wemccaug
  2. From: wemccaug@prairienet.org (Wendy E. McCaughrin)
  3. Newsgroups: comp.lang.c++
  4. Subject: Re: Fastest Sorting Algorithm?
  5. Date: 14 Apr 1996 00:09:17 GMT
  6. Organization: University of Illinois at Urbana
  7. Message-ID: <4kpfnd$3ed@vixen.cso.uiuc.edu>
  8. References: <4k680p$6fs@longwood.cs.ucf.edu> <Dou55w.7MB@novice.uwaterloo.ca> <DpAxtI.3w9@undergrad.math.uwaterloo.ca> <4k4unk$15q
  9. Reply-To: wemccaug@prairienet.org (Wendy E. McCaughrin)
  10. NNTP-Posting-Host: firefly.prairienet.org
  11.  
  12.  
  13. >
  14. >Is it really 2logn?  My understanding was that a sort couldn't be
  15. >less than nlogn...  More info, please.
  16. >
  17.  You are correct: Quicksort performance is O(n*log(n)), usually
  18.  written: O(nlog n). The analysis to obtain its performance com-
  19.  monly show O(n*lg(n)), with "lg' meaning log, base 2. But if
  20.  b is any other acceptable base and "log" means log, base b:
  21.  lg(n) = log(n)/log(2) and n*lg(n) = (1/log(2))*n*log(n). When
  22.  the only difference is a constant of proportionality (1/log(2)),
  23.  then O(n*lg(n)) is O(n*log(n)).
  24.  
  25.